#define _CRT_SECURE_NO_WARNINGS 1
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
bool ans;
int n, m;
bool st[110][110];
class Solution {
public:

    void dfs(int x, int y, vector<string>& board, string word, int pos) {
        if (pos == word.size()) {
            ans = true;
            return;
        }

        for (int i = 0; i < 4; i++) {
            int a = dx[i] + x;
            int b = dy[i] + y;
            if (a >= 0 && a < n && b >= 0 && b < m && board[a][b] == word[pos] && !st[a][b]) {
                st[a][b] = true;
                dfs(a, b, board, word, pos + 1);
                st[a][b] = false;
            }
        }
    }

    bool exist(vector<string>& board, string word) {
        n = board.size();
        m = board[0].size();
        ans = false;
        memset(st, false, sizeof st);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == word[0]) {
                    st[i][j] = true;
                    dfs(i, j, board, word, 1);
                    st[i][j] = false;
                    if (ans)return true;
                }
            }
        }
        return false;

    }
};